{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# arc_flow_cutting_stock_sat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/examples/arc_flow_cutting_stock_sat.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/python/arc_flow_cutting_stock_sat.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Cutting stock problem with the objective to minimize wasted space.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "import time\n",
    "\n",
    "from ortools.sat.colab import flags\n",
    "import numpy as np\n",
    "\n",
    "from google.protobuf import text_format\n",
    "from ortools.linear_solver.python import model_builder as mb\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "_OUTPUT_PROTO = flags.define_string(\n",
    "    \"output_proto\", \"\", \"Output file to write the cp_model proto to.\"\n",
    ")\n",
    "_PARAMS = flags.define_string(\n",
    "    \"params\",\n",
    "    \"num_search_workers:8,log_search_progress:true,max_time_in_seconds:10\",\n",
    "    \"Sat solver parameters.\",\n",
    ")\n",
    "_SOLVER = flags.define_string(\"solver\", \"sat\", \"Method used to solve: sat, mip.\")\n",
    "\n",
    "\n",
    "DESIRED_LENGTHS = [\n",
    "    2490,\n",
    "    3980,\n",
    "    2490,\n",
    "    3980,\n",
    "    2391,\n",
    "    2391,\n",
    "    2391,\n",
    "    596,\n",
    "    596,\n",
    "    596,\n",
    "    2456,\n",
    "    2456,\n",
    "    3018,\n",
    "    938,\n",
    "    3018,\n",
    "    938,\n",
    "    943,\n",
    "    3018,\n",
    "    943,\n",
    "    3018,\n",
    "    2490,\n",
    "    3980,\n",
    "    2490,\n",
    "    3980,\n",
    "    2391,\n",
    "    2391,\n",
    "    2391,\n",
    "    596,\n",
    "    596,\n",
    "    596,\n",
    "    2456,\n",
    "    2456,\n",
    "    3018,\n",
    "    938,\n",
    "    3018,\n",
    "    938,\n",
    "    943,\n",
    "    3018,\n",
    "    943,\n",
    "    3018,\n",
    "    2890,\n",
    "    3980,\n",
    "    2890,\n",
    "    3980,\n",
    "    2391,\n",
    "    2391,\n",
    "    2391,\n",
    "    596,\n",
    "    596,\n",
    "    596,\n",
    "    2856,\n",
    "    2856,\n",
    "    3018,\n",
    "    938,\n",
    "    3018,\n",
    "    938,\n",
    "    943,\n",
    "    3018,\n",
    "    943,\n",
    "    3018,\n",
    "    3290,\n",
    "    3980,\n",
    "    3290,\n",
    "    3980,\n",
    "    2391,\n",
    "    2391,\n",
    "    2391,\n",
    "    596,\n",
    "    596,\n",
    "    596,\n",
    "    3256,\n",
    "    3256,\n",
    "    3018,\n",
    "    938,\n",
    "    3018,\n",
    "    938,\n",
    "    943,\n",
    "    3018,\n",
    "    943,\n",
    "    3018,\n",
    "    3690,\n",
    "    3980,\n",
    "    3690,\n",
    "    3980,\n",
    "    2391,\n",
    "    2391,\n",
    "    2391,\n",
    "    596,\n",
    "    596,\n",
    "    596,\n",
    "    3656,\n",
    "    3656,\n",
    "    3018,\n",
    "    938,\n",
    "    3018,\n",
    "    938,\n",
    "    943,\n",
    "    3018,\n",
    "    943,\n",
    "    3018,\n",
    "    2790,\n",
    "    3980,\n",
    "    2790,\n",
    "    3980,\n",
    "    2391,\n",
    "    2391,\n",
    "    2391,\n",
    "    596,\n",
    "    596,\n",
    "    596,\n",
    "    2756,\n",
    "    2756,\n",
    "    3018,\n",
    "    938,\n",
    "    3018,\n",
    "    938,\n",
    "    943,\n",
    "    3018,\n",
    "    943,\n",
    "    3018,\n",
    "    2790,\n",
    "    3980,\n",
    "    2790,\n",
    "    3980,\n",
    "    2391,\n",
    "    2391,\n",
    "    2391,\n",
    "    596,\n",
    "    596,\n",
    "    596,\n",
    "    2756,\n",
    "    2756,\n",
    "    3018,\n",
    "    938,\n",
    "    3018,\n",
    "    938,\n",
    "    943,\n",
    "]\n",
    "POSSIBLE_CAPACITIES = [4000, 5000, 6000, 7000, 8000]\n",
    "\n",
    "# Toy problem\n",
    "# DESIRED_LENGTHS = [12, 12, 8, 8, 8]\n",
    "# POSSIBLE_CAPACITIES = [10, 20]\n",
    "\n",
    "\n",
    "def regroup_and_count(raw_input):\n",
    "    \"\"\"Regroup all equal capacities in a multiset.\"\"\"\n",
    "    grouped = collections.defaultdict(int)\n",
    "    for i in raw_input:\n",
    "        grouped[i] += 1\n",
    "    output = []\n",
    "    for size, count in grouped.items():\n",
    "        output.append([size, count])\n",
    "    output.sort(reverse=False)\n",
    "    return output\n",
    "\n",
    "\n",
    "def price_usage(usage, capacities):\n",
    "    \"\"\"Compute the best price for a given usage and possible capacities.\"\"\"\n",
    "    price = max(capacities)\n",
    "    for capacity in capacities:\n",
    "        if capacity < usage:\n",
    "            continue\n",
    "        price = min(capacity - usage, price)\n",
    "    return price\n",
    "\n",
    "\n",
    "def create_state_graph(items, max_capacity):\n",
    "    \"\"\"Create a state graph from a multiset of items, and a maximum capacity.\"\"\"\n",
    "    states = []\n",
    "    state_to_index = {}\n",
    "    states.append(0)\n",
    "    state_to_index[0] = 0\n",
    "    transitions = []\n",
    "\n",
    "    for item_index, size_and_count in enumerate(items):\n",
    "        size, count = size_and_count\n",
    "        num_states = len(states)\n",
    "        for state_index in range(num_states):\n",
    "            current_state = states[state_index]\n",
    "            current_state_index = state_index\n",
    "\n",
    "            for card in range(count):\n",
    "                new_state = current_state + size * (card + 1)\n",
    "                if new_state > max_capacity:\n",
    "                    break\n",
    "                if new_state in state_to_index:\n",
    "                    new_state_index = state_to_index[new_state]\n",
    "                else:\n",
    "                    new_state_index = len(states)\n",
    "                    states.append(new_state)\n",
    "                    state_to_index[new_state] = new_state_index\n",
    "                # Add the transition\n",
    "                transitions.append(\n",
    "                    [current_state_index, new_state_index, item_index, card + 1]\n",
    "                )\n",
    "\n",
    "    return states, transitions\n",
    "\n",
    "\n",
    "def solve_cutting_stock_with_arc_flow_and_sat(output_proto_file: str, params: str):\n",
    "    \"\"\"Solve the cutting stock with arc-flow and the CP-SAT solver.\"\"\"\n",
    "    items = regroup_and_count(DESIRED_LENGTHS)\n",
    "    print(\"Items:\", items)\n",
    "    num_items = len(DESIRED_LENGTHS)\n",
    "\n",
    "    max_capacity = max(POSSIBLE_CAPACITIES)\n",
    "    states, transitions = create_state_graph(items, max_capacity)\n",
    "\n",
    "    print(\n",
    "        \"Dynamic programming has generated\",\n",
    "        len(states),\n",
    "        \"states and\",\n",
    "        len(transitions),\n",
    "        \"transitions\",\n",
    "    )\n",
    "\n",
    "    incoming_vars = collections.defaultdict(list)\n",
    "    outgoing_vars = collections.defaultdict(list)\n",
    "    incoming_sink_vars = []\n",
    "    item_vars = collections.defaultdict(list)\n",
    "    item_coeffs = collections.defaultdict(list)\n",
    "    transition_vars = []\n",
    "\n",
    "    model = cp_model.CpModel()\n",
    "\n",
    "    objective_vars = []\n",
    "    objective_coeffs = []\n",
    "\n",
    "    for outgoing, incoming, item_index, card in transitions:\n",
    "        count = items[item_index][1]\n",
    "        max_count = count // card\n",
    "        count_var = model.NewIntVar(\n",
    "            0, max_count, \"i%i_f%i_t%i_C%s\" % (item_index, incoming, outgoing, card)\n",
    "        )\n",
    "        incoming_vars[incoming].append(count_var)\n",
    "        outgoing_vars[outgoing].append(count_var)\n",
    "        item_vars[item_index].append(count_var)\n",
    "        item_coeffs[item_index].append(card)\n",
    "        transition_vars.append(count_var)\n",
    "\n",
    "    for state_index, state in enumerate(states):\n",
    "        if state_index == 0:\n",
    "            continue\n",
    "        exit_var = model.NewIntVar(0, num_items, \"e%i\" % state_index)\n",
    "        outgoing_vars[state_index].append(exit_var)\n",
    "        incoming_sink_vars.append(exit_var)\n",
    "        price = price_usage(state, POSSIBLE_CAPACITIES)\n",
    "        objective_vars.append(exit_var)\n",
    "        objective_coeffs.append(price)\n",
    "\n",
    "    # Flow conservation\n",
    "    for state_index in range(1, len(states)):\n",
    "        model.Add(sum(incoming_vars[state_index]) == sum(outgoing_vars[state_index]))\n",
    "\n",
    "    # Flow going out of the source must go in the sink\n",
    "    model.Add(sum(outgoing_vars[0]) == sum(incoming_sink_vars))\n",
    "\n",
    "    # Items must be placed\n",
    "    for item_index, size_and_count in enumerate(items):\n",
    "        num_arcs = len(item_vars[item_index])\n",
    "        model.Add(\n",
    "            sum(\n",
    "                item_vars[item_index][i] * item_coeffs[item_index][i]\n",
    "                for i in range(num_arcs)\n",
    "            )\n",
    "            == size_and_count[1]\n",
    "        )\n",
    "\n",
    "    # Objective is the sum of waste\n",
    "    model.Minimize(\n",
    "        sum(objective_vars[i] * objective_coeffs[i] for i in range(len(objective_vars)))\n",
    "    )\n",
    "\n",
    "    # Output model proto to file.\n",
    "    if output_proto_file:\n",
    "        model.ExportToFile(output_proto_file)\n",
    "\n",
    "    # Solve model.\n",
    "    solver = cp_model.CpSolver()\n",
    "    if params:\n",
    "        text_format.Parse(params, solver.parameters)\n",
    "    solver.parameters.log_search_progress = True\n",
    "    solver.Solve(model)\n",
    "\n",
    "\n",
    "def solve_cutting_stock_with_arc_flow_and_mip():\n",
    "    \"\"\"Solve the cutting stock with arc-flow and a MIP solver.\"\"\"\n",
    "    items = regroup_and_count(DESIRED_LENGTHS)\n",
    "    print(\"Items:\", items)\n",
    "    num_items = len(DESIRED_LENGTHS)\n",
    "    max_capacity = max(POSSIBLE_CAPACITIES)\n",
    "    states, transitions = create_state_graph(items, max_capacity)\n",
    "\n",
    "    print(\n",
    "        \"Dynamic programming has generated\",\n",
    "        len(states),\n",
    "        \"states and\",\n",
    "        len(transitions),\n",
    "        \"transitions\",\n",
    "    )\n",
    "\n",
    "    incoming_vars = collections.defaultdict(list)\n",
    "    outgoing_vars = collections.defaultdict(list)\n",
    "    incoming_sink_vars = []\n",
    "    item_vars = collections.defaultdict(list)\n",
    "    item_coeffs = collections.defaultdict(list)\n",
    "\n",
    "    start_time = time.time()\n",
    "    model = mb.ModelBuilder()\n",
    "\n",
    "    objective_vars = []\n",
    "    objective_coeffs = []\n",
    "\n",
    "    var_index = 0\n",
    "    for outgoing, incoming, item_index, card in transitions:\n",
    "        count = items[item_index][1]\n",
    "        count_var = model.new_int_var(\n",
    "            0,\n",
    "            count,\n",
    "            \"a%i_i%i_f%i_t%i_c%i\" % (var_index, item_index, incoming, outgoing, card),\n",
    "        )\n",
    "        var_index += 1\n",
    "        incoming_vars[incoming].append(count_var)\n",
    "        outgoing_vars[outgoing].append(count_var)\n",
    "        item_vars[item_index].append(count_var)\n",
    "        item_coeffs[item_index].append(card)\n",
    "\n",
    "    for state_index, state in enumerate(states):\n",
    "        if state_index == 0:\n",
    "            continue\n",
    "        exit_var = model.new_int_var(0, num_items, \"e%i\" % state_index)\n",
    "        outgoing_vars[state_index].append(exit_var)\n",
    "        incoming_sink_vars.append(exit_var)\n",
    "        price = price_usage(state, POSSIBLE_CAPACITIES)\n",
    "        objective_vars.append(exit_var)\n",
    "        objective_coeffs.append(price)\n",
    "\n",
    "    # Flow conservation\n",
    "    for state_index in range(1, len(states)):\n",
    "        model.add(\n",
    "            mb.LinearExpr.sum(incoming_vars[state_index])\n",
    "            == mb.LinearExpr.sum(outgoing_vars[state_index])\n",
    "        )\n",
    "\n",
    "    # Flow going out of the source must go in the sink\n",
    "    model.add(\n",
    "        mb.LinearExpr.sum(outgoing_vars[0]) == mb.LinearExpr.sum(incoming_sink_vars)\n",
    "    )\n",
    "\n",
    "    # Items must be placed\n",
    "    for item_index, size_and_count in enumerate(items):\n",
    "        num_arcs = len(item_vars[item_index])\n",
    "        model.add(\n",
    "            mb.LinearExpr.sum(\n",
    "                [\n",
    "                    item_vars[item_index][i] * item_coeffs[item_index][i]\n",
    "                    for i in range(num_arcs)\n",
    "                ]\n",
    "            )\n",
    "            == size_and_count[1]\n",
    "        )\n",
    "\n",
    "    # Objective is the sum of waste\n",
    "    model.minimize(np.dot(objective_vars, objective_coeffs))\n",
    "\n",
    "    solver = mb.ModelSolver(\"scip\")\n",
    "    solver.enable_output(True)\n",
    "    status = solver.solve(model)\n",
    "\n",
    "    ### Output the solution.\n",
    "    if status == mb.SolveStatus.OPTIMAL or status == mb.SolveStatus.FEASIBLE:\n",
    "        print(\n",
    "            \"Objective value = %f found in %.2f s\"\n",
    "            % (solver.objective_value, time.time() - start_time)\n",
    "        )\n",
    "    else:\n",
    "        print(\"No solution\")\n",
    "\n",
    "\n",
    "def main(_):\n",
    "    \"\"\"Main function.\"\"\"\n",
    "    if _SOLVER.value == \"sat\":\n",
    "        solve_cutting_stock_with_arc_flow_and_sat(_OUTPUT_PROTO.value, _PARAMS.value)\n",
    "    else:  # 'mip'\n",
    "        solve_cutting_stock_with_arc_flow_and_mip()\n",
    "\n",
    "\n",
    "main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
